1. Field of the Invention
The present invention relates to an error correction decoding apparatus for correcting a code error in transmitted code data.
2. Related Background Art
Recently, the density of digital recording has increased steadily, and an error correction encoding/decoding apparatus which can operate at a high speed and has high correction performance is in demand accordingly.
A Reed-Solomon code is a kind of a BCH code and has high correction performance because it can be corrected in units of bytes. Accordingly, a Reed-Solomon code is extensively used in a variety of fields such as an optical disk and a digital VTR.
The principle of a representative decoding method for a Reed-Solomon code will be briefly described below.
A q-element Reed-Solomon code having .alpha. as a primitive element of GF(q) and 1, .alpha., .alpha..sup.2, . . . , .alpha..sup.d-2 as a root of a generator polynomial G(x) will be taken as an example. Code length n=q-1, information symbol number k=q-d, and minimum distance d.sub.min =d.
First, a syndrome Si is calculated from a received polynomial Y(x) from equation (1) below. EQU S.sub.i =Y(.alpha..sup.i)=E(.alpha..sup.i)(i=0, 1, . . . , d-2)(1)
where E(x) is a polynomial representing an error pattern.
Assume that one error occurs in a position j.sub.1, j.sub.2, . . . , j.sub.1. Note that EQU n-1.gtoreq.j.sub.1 &gt;j.sub.2 &gt; . . . &gt;j.sub.1 .gtoreq.0 (2) EQU 1.ltoreq.t=.left brkt-top.(d-1)/2.right brkt-bot. (3)
where .left brkt-top.x.right brkt-bot. is a maximum integer smaller than x and t indicates the error correction performance.
If this is the case, an error pattern polynomial E(x) is represented by EQU E(x)=E.sub.1 x.sup.j1 +E.sub.2 x.sup.j2 + . . . +E.sub.1 x.sup.j1(4)
E.sub.i (i=1, . . . , 1) is the value of an error in a position j.sub.i and the element of GF(q). The syndrome S.sub.i is rewritten from equation (1) as follows. EQU S.sub.i =E.sub.1 x.sup.i.sub.1 +E.sub.2 x.sup.i.sub.2 + . . . +E.sub.1 x.sup.i.sub.1 (5) EQU for x.sub.i =.alpha..sup.ji (i=1, . . . , 1) (6)
A Reed-Solomon code is decoded by calculating the error positions j.sub.1, j.sub.2, . . . , j.sub.1 and the error values E.sub.1, E.sub.2, . . . , E.sub.1 from the syndrome S.sub.i. For this purpose, two polynomials ##EQU1## on GF(q) are calculated. These polynomials have .alpha..sup.-j1, .alpha..sup.-j2, . . . , .alpha..sup.-j1 as a root. .sigma.(z) is called an error position polynomial, and .eta.(z) is a polynomial required to calculate the error value and is called an error evaluation polynomial.
Consider the following polynomial having the syndrome as a coefficient. EQU S(z)=S.sub.d2 Z.sup.d-2 + . . . +S.sub.1 z+S.sub.0 (9)
The relationship between the syndrome polynomial, .sigma.(z), and .eta.(z) can be written as follows. EQU .sigma.(z)S(z).ident..eta.(z)mod z.sup.d-1 (10)
This is a fundamental equation from which .sigma.(z) and .eta.(z) can be calculated.
When the error correction performance t is 4 to 5, a method based on a Euclidean method of mutual division can be used as a method of efficiently calculating .sigma.(z) and .eta.(z). This method will be referred to as a Euclidean algorithm hereinafter. Equation (10) can be rewritten as follows by using an appropriate polynomial A(z). EQU A(z)z.sup.d- +.sigma.(z)S(z)=.eta.(z) (11)
Since it is assumed that the error number 1 is t or less, the following equation must hold. EQU deg.eta.(z)&lt;deg.sigma.(z).ltoreq.t (12)
where deg is the degree of a polynomial.
As is apparent from equations (8) and (7), .sigma.(z) and .eta.(z) have no common factor. It is proved that .sigma.(z) and .eta.(z) that satisfy equation (12) can be uniquely determined. Also, it is known that such .sigma.(z) and .eta.(z) can be calculated by the Euclidean algorithm for calculating the greatest common divisor polynomial of z.sup.d- and S(z). FIG. 1 shows a general method of the Euclidean algorithm.
As a method of obtaining the root of .sigma.(z) calculated by the Euclidean algorithm, chien search is generally used. Chien search is a method by which power .alpha..sup.i (i=0, 1, . . . , n-1) of .alpha. is sequentially substituted into .sigma.(z) and whether .sigma.(.alpha..sup.i) equals 0 is checked.
Error values e.sub.1, e.sub.2 . . . , e.sub.1 can be calculated as follows. EQU e.sub.i =-.eta.(.alpha..sup.-ji)/.sigma.(.alpha..sup.-ji)'(i=1, . . . , 1)(13)
where .sigma.(z)' is a derived function of .sigma.(z) an calculated by formally differentiating .sigma.(z).
Conventionally, the individual steps of the above correction processing are generally pipelined and constituted by hardware.
FIG. 2 shows an example of the arrangement of a conventional Reed-Solomon code error correction decoding apparatus. Referring to FIG. 2, input data containing an error correction encoded error from an input terminal 600 is delayed by a processing time (to be described below) by a data delay circuit 601. At the same time, a syndrome operation circuit 602 calculates the syndrome S.sub.i in accordance with equation (1). This syndrome S.sub.i is supplied as the syndrome polynomial represented by equation (2) to a Galois field polynomial operation circuit 603.
The Galois field polynomial operation circuit 603 calculates the error position polynomial .sigma.(z) and the error value polynomial .eta.(z) by using the Euclidean algorithm shown in FIG. 1. In this Euclidean algorithm, primarily a quotient polynomial and a remainder polynomial of a Galois field polynomial are repeatedly calculated. The error position polynomial .sigma.(z) satisfying a comparison condition of degR(z)&lt;t-1 in the Galois field polynomial operation circuit 603 is supplied to a chien search circuit 604.
The chien search circuit 604 sequentially substitutes elements of a Galois field GF(2.sup.m) and checks whether each resultant value equals 0, thereby calculating a root. The chien search circuit 604 then supplies error position information i, the error value .eta.(z), and the value .sigma.(z)' calculated by formally differentiating the error position to an error value calculation circuit 605. The error value calculation circuit 605 calculates the error value e.sub.i from the error position information i calculated by the chien search circuit 604 and equation (13).
The error position and value thus calculated are supplied to a correction circuit 606. The correction circuit 606 performs correction processing by calculating exclusive OR of the error position in the data sequence delayed by the data delay circuit 601 and the calculated error value. The correction circuit 606 outputs the result from an output terminal 607.
In the above conventional arrangement, however, although high-speed processing is accomplished by constituting all blocks by hardware, the circuit scale inevitably increases. Additionally, the hardware configuration of the control block must be changed whenever the algorithm is altered for, e.g., complicated repetitive decoding including erasure correction of product-modulated data.